package LeetCode刷题;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-11-07 16:32
 * @description: Functions of this class is
 * 官方题解：
 * class Solution {
 *     public int nthUglyNumber(int n) {
 *         int dp[]=new int[n+1];//设置一个数组存储前n个丑数
 *         dp[1]=1;//第一个丑数为1
 *         //设置三个指针，其分别代表2，3，5三个乘数下得到的丑数的索引下标
 *         int u2=1;
 *         int u3=1;
 *         int u5=1;
 *         for(int i=2;i<=n;i++){
 *             //获得当前2，3，5索引下的各个丑数，每次取三个丑数中最小的，然后改丑数的索引就能向前走，
 *             //这样就能保证这些丑数都是按升序来排列的，而且也不会重复，
 *             //假如就只是每次将各个丑数*2 *3 *5的话，有可能出现后面乘到的比前面的更小不满足升序，也有可能出现前面的丑数后面再次出现
 *             //所以使用下面三个指针来标记说，就比如说*2的索引u2说明：当前丑数如果要取*2的 ，就要从当前数组中的u2索引下的元素去乘，前面的以及乘过了
 *
 *             int num2=dp[u2]*2;
 *             int num3=dp[u3]*3;
 *             int num5=dp[u5]*5;
 *             dp[i]=Math.min(num2,Math.min(num3,num5));
 *             if(dp[i]==num2){
 *                 u2++;
 *             }
 *             if(dp[i]==num3){
 *                 u3++;
 *             }
 *             if(dp[i]==num5){
 *                 u5++;
 *             }
 *         }
 *         return dp[n];
 *     }
 * }
 **/
public class No动态规划丑数II {
    public static void main(String args[]){

    }
}